package com.cande.loki.exercise.algorithm;

import java.util.*;

/**
 * 深度优先
 */
public class DFSDemo {
    // 使用邻接列表表示图
    private Map<Integer, List<Integer>> adjList = new HashMap<>();

    // 构造函数，初始化图
    public DFSDemo() {
        // 假设图结构如下：
        // 1 -> 2, 3
        // 2 -> 4
        // 3 -> 5
        adjList.put(1, Arrays.asList(2, 3));
        adjList.put(2, Arrays.asList(4));
        adjList.put(3, Arrays.asList(5));
        adjList.put(4, new ArrayList<>());
        adjList.put(5, new ArrayList<>());
    }

    // 深度优先搜索的递归实现
    public void dfs(int node, Set<Integer> visited) {
        // 访问节点
        System.out.println("Visited: " + node);
        visited.add(node); // 标记为已访问

        // 递归地访问相邻节点
        for (int neighbor : adjList.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                dfs(neighbor, visited);
            }
        }
    }


    // 深度优先搜索的栈实现
    public void dfs(int start) {
        Set<Integer> visited = new HashSet<>(); // 记录已访问的节点
        Stack<Integer> stack = new Stack<>();   // 用栈来记录访问的节点
        stack.push(start);                      // 起始节点压栈

        while (!stack.isEmpty()) {
            int node = stack.pop();

            if (!visited.contains(node)) {
                // 访问节点
                System.out.println("Visited: " + node);
                visited.add(node); // 标记为已访问

                // 将相邻节点压栈（注意要从最后一个相邻节点开始）
                List<Integer> neighbors = adjList.getOrDefault(node, new ArrayList<>());
                for (int i = neighbors.size() - 1; i >= 0; i--) {
                    stack.push(neighbors.get(i));
                }
            }
        }
    }



    public static void main(String[] args) {
        DFSDemo graph = new DFSDemo();
        Set<Integer> visited = new HashSet<>();
        System.out.println("DFS Recursive Traversal:");
        graph.dfs(1, visited); // 从节点 1 开始深度优先搜索  深度优先搜索的递归实现

        graph.dfs(1); // 从节点 1 开始深度优先搜索  深度优先搜索的栈实现
    }
}
